CF321E Ciel and Gondolas

各位大佬都用的 wqswqs 二分,蒟蒻介绍一种简单方法。

dpdp 式很好列:

dp[i][j]=min(dp[i1][k1]+calc(k,j))dp[i][j]=min( dp[i-1][k-1] + calc( k , j ) )

calc(k,j)calc(k,j)表示将 kkjj 的贞鱼在同一车的怨气值 , 决策具有单调性。

不如将当前的决策点区间记为 $ [optl,optr] $ , 处理 dpdp 的区间为 $ [L,R] $

我们可以暴力计算 dp[s][mid]dp[s][mid] 的值 (mid=L+R2)(mid=\frac{L+R}{2}) , 并记录当前的决策点optopt

然后我们可以递归计算 dp[s][l...(mid1)]dp[s][l...(mid-1)]dp[s][(mid+1)...r]dp[s][(mid+1)...r]

因为决策具有单调性 , 所以计算 dp[s][l...(mid1)]dp[s][l...(mid-1)]时只需用[optl,opt][optl,opt] , 计算 dp[s][(mid+1)...r]dp[s][(mid+1)...r]时只需用[opt,optr][opt,optr]

这种方法仅适用于有决策单调性的题,时间复杂度为Θ(knlogn)\Theta(k*n*\log n)

#include <cstdio>
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f

void Read( int &x ) {
	x = 0; int f = 1;
	char s = getchar( );
	for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
	for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
	x *= f;
}
void Write( int x ) {
	if( x < 0 )
		putchar('-') , x = -x;
	if( x >= 10 ) Write( x / 10 );
	putchar( x % 10 + '0' );
}

const int MAXK = 800 , MAXN = 4000;
int n , k , x , sum[ MAXN + 5 ][ MAXN + 5 ];
int dp[ MAXK + 5 ][ MAXN + 5 ];

int Calc( int u , int v ) {
	return sum[ v ][ v ] - sum[ v ][ u - 1 ] - sum[ u - 1 ][ v ] + sum[ u - 1 ][ u - 1 ];
}
void dfs( int s , int L , int R , int optl , int optr ) {
	if( L > R ) return;
	
	int Mid = ( L + R ) / 2 , opt;
	dp[ s ][ Mid ] = INF;
	for( int i = optl ; i <= min( optr , Mid ) ; i ++ ) {
		if( dp[ s ][ Mid ] > dp[ s - 1 ][ i - 1 ] + Calc( i , Mid ) ) {
			dp[ s ][ Mid ] = dp[ s - 1 ][ i - 1 ] + Calc( i , Mid );
			opt = i;
		}
	}
	dfs( s , L , Mid - 1 , optl , opt );
	dfs( s , Mid + 1 , R , opt , optr );
}

int main( ) {
	Read( n ) , Read( k );
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= n ; j ++ )
			Read( x ) , sum[ i ][ j ] = sum[ i - 1 ][ j ] + sum[ i ][ j - 1 ] - sum[ i - 1 ][ j - 1 ] + x;
	for( int i = 1 ; i <= n ; i ++ )
		dp[ 0 ][ i ] = INF;
	for( int i = 1 ; i <= k ; i ++ )
		dfs( i , 1 , n , 1 , n );
	Write( dp[ k ][ n ] / 2 );
	return 0;
}